package com.gxc.array;

import java.util.*;

/**
 * 2101. 引爆最多的炸弹
 * 给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。
 *
 * 炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [xi, yi, ri] 。
 * xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标，ri 表示爆炸范围的 半径 。
 *
 * 你需要选择引爆 一个 炸弹。
 * 当这个炸弹被引爆时，所有 在它爆炸范围内的炸弹都会被引爆，这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。
 *
 * 给你数组 bombs ，请你返回在引爆 一个 炸弹的前提下，最多 能引爆的炸弹数目。
 */
public class MaximumDetonation {

    public static void main(String[] args) {
        System.out.println(handle(new int[][]{
                {2,1,3},
                {6,1,4}
        }));

        System.out.println(handle(new int[][]{
                {1,1,5},
                {10,10,5}
        }));

        System.out.println(handle(new int[][]{
                {1,2,3},
                {2,3,1},
                {3,4,2},
                {4,5,3},
                {5,6,4}
        }));
    }

    public static int handle(int[][] bombs) {
        //构建有向图
        Map<Integer, List<Integer>> edges = new HashMap<>();
        for (int i = 0; i < bombs.length; i++) {
            for (int j = 0; j < bombs.length; j++) {
                if (i!=j && isInPark(i, j, bombs)) {
                    edges.putIfAbsent(i, new ArrayList<>());
                    edges.get(i).add(j);
                }
            }
        }
        if (edges.size() == 0) return 1;

        //有向图中查找可以走最多的点
        int res = 0;
        Iterator<Integer> iterator = edges.keySet().iterator();
        //已经计算过的路径快速跳过
        Map<Integer,  Set<Integer>> map = new HashMap<>();
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            Set<Integer> set = new HashSet<>();
            Queue<Integer> queue = new ArrayDeque<>();
            queue.add(next);
            while (!queue.isEmpty()) {
                Integer poll = queue.poll();
                if (map.get(poll) == null) {
                    set.add(poll);
                    List<Integer> list = edges.get(poll);
                    if (list != null) {
                        for (Integer i : list) {
                            if (!set.contains(i)) {
                                queue.add(i);
                            }
                        }
                    }
                } else {
                    set.addAll(map.get(poll));
                }


            }
            map.put(next, set);
            res = Math.max(res, set.size());
        }
        return res;
    }

    /**
     * j 是否在 i的园内
     * @param i
     * @param j
     * @param bombs
     * @return
     */
    private static boolean isInPark(int i, int j, int[][] bombs) {
        long x = bombs[i][0] - bombs[j][0];
        long y = bombs[i][1] - bombs[j][1];
        //半径
        long r = bombs[i][2];
        return r*r >= x*x + y*y;
    }

    class Solution {
        public int maximumDetonation(int[][] bombs) {
            int n = bombs.length;
            // 维护引爆关系有向图
            Map<Integer, List<Integer>> edges = new HashMap<Integer, List<Integer>>();
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (i != j && isConnected(bombs, i, j)) {
                        edges.putIfAbsent(i, new ArrayList<Integer>());
                        edges.get(i).add(j);
                    }
                }
            }
            int res = 0;   // 最多引爆数量
            for (int i = 0; i < n; ++i) {
                // 遍历每个炸弹，广度优先搜索计算该炸弹可引爆的数量，并维护最大值
                boolean[] visited = new boolean[n];
                int cnt = 1;
                Queue<Integer> queue = new ArrayDeque<Integer>();
                queue.offer(i);
                visited[i] = true;
                while (!queue.isEmpty()) {
                    int cidx = queue.poll();
                    for (int nidx : edges.getOrDefault(cidx, new ArrayList<Integer>())) {
                        if (visited[nidx]) {
                            continue;
                        }
                        ++cnt;
                        queue.offer(nidx);
                        visited[nidx] = true;
                    }
                }
                res = Math.max(res, cnt);
            }
            return res;
        }

        // 判断炸弹 u 能否引爆炸弹 v
        public boolean isConnected(int[][] bombs, int u, int v) {
            long dx = bombs[u][0] - bombs[v][0];
            long dy = bombs[u][1] - bombs[v][1];
            return (long) bombs[u][2] * bombs[u][2] >= dx * dx + dy * dy;
        }
    }



}
